123. 买卖股票的最佳时机 III

Similar Question

Solution Tips

方案一: 回溯 + 记忆化搜索

var maxProfit = function(prices) {
    // dp[i][0] dp[i][1] 据说是股票问题的通用解, 那就按照这个来呗
    // 在第 i 天的时候, 持有股票 or 持有现金, 所能拥有的最大金额 (现金)
    // II 是可以多次买卖, III 是只能买卖最多 2 次
    // 先找出所有能获得收益的交易时机? 然后合法的挑选2次即可
    // 那不就是限制 dp[i][0] 吗? 因为 0 就是不持有股票的时候

    // 直接走回溯法解决了
    // 找出所有的能买卖股票的时机, 然后合法的挑选2次
    // 如何做记忆化呢? 针对单次 profit ? 针对总的 profit ?
    // 总之是要让收益最大化, 那就是 cur 做出选择时, 最大的那个, 才是我们想要的
    // 最重要的是确定重复, 只要 curIndex、sellCount 一致, 能获得的最大利润就是固定的
    // 要返回的是单笔的利润, 只有单笔的利润是可以复用的
    // 对于 sellCount 为 0 的, 返回的是2笔的利润
    // 对于 sellCount 为 1 的, 返回的是单笔的利润
    // 对于 sellCount 为 2 的, 返回 0
    // 所以我要保存的事, 当前状态下能额外获得的最大利润
    const map = Array.from({ length: prices.length }, () => Array.from({length: 3}));

    return backtracking(0, 0);


    function backtracking(cur, sellCount) {
        if (cur >= prices.length) return 0;

        if (sellCount === 2) return 0;

        if (map[cur][sellCount] !== undefined) return map[cur][sellCount];

        // 买入当前股票
        const stock = prices[cur];
        let max1 = 0;
        for (let i = cur + 1; i < prices.length; i++) {
            // 只要大于买入价格, 都可以选择卖出
            if (prices[i] > stock) {
                //  选择卖出
                sellCount++;
                // 寻找下一次买入的时机
                max1 = Math.max(max1, prices[i] - stock + backtracking(i + 1 ,sellCount));
                // 回溯, 下一轮可以继续卖出
                sellCount--;
            }
        }
        // 选择买入当前股票后的最大收益
        // 打印出来之后, 能看到多次重复的, 这些重复的就是可以优化的地方
        // 不买入当前股票, 直接从下一次开始
        const max2 = backtracking(cur + 1 ,sellCount);
        // 两种方案里的更大者, 才是最佳决策
        const max = Math.max(max1, max2);
        map[cur][sellCount] = max;
        // console.log('max: ', cur, sellCount, max);
        return max;
    }
};
console.log(maxProfit([3,2,6,5,0,3]));

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int n = prices.length;
        return dfs(prices,0,0,0);
    }
	
    private int dfs(int[] prices,int index,int status,int k) {
        //递归终止条件，数组执行到头了，或者交易了两次了
        if(index==prices.length || k==2) {
            return 0;
        }
        //定义三个变量，分别记录[不动]、[买]、[卖]
        int a=0,b=0,c=0;
        //保持不动
        a = dfs(prices,index+1,status,k);
        if(status==1) {
            //递归处理卖的情况，这里需要将k+1，表示执行了一次交易
            b = dfs(prices,index+1,0,k+1)+prices[index];
        }
        else {
            //递归处理买的情况
            c = dfs(prices,index+1,1,k)-prices[index];
        }
        //最终结果就是三个变量中的最大值
        return Math.max(Math.max(a,b),c);
    }
}

方案二: 从暴力法出发的动态规划

行不通

方案三: 从状态讨论出的动态规划

代码随想录

确定 Dp 数组以及下标的含义

一天一共就有五个状态:

0. 没有操作 （其实我们也可以不设置这个状态）
1. 第一次持有股票
2. 第一次不持有股票
3. 第二次持有股票
4. 第二次不持有股票

const maxProfit = prices => {
    const len = prices.length;
    const dp = new Array(len).fill(0).map(x => new Array(5).fill(0));
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];
    for (let i = 1; i < len; i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[len - 1][4];
};

const maxProfit = prices => {
    const len = prices.length;
    const dp = new Array(5).fill(0);
    dp[1] = -prices[0];
    dp[3] = -prices[0];
    for (let i = 1; i < len; i++) {
        dp[1] = Math.max(dp[1], dp[0] - prices[i]);
        dp[2] = Math.max(dp[2], dp[1] + prices[i]);
        dp[3] = Math.max(dp[3], dp[2] - prices[i]);
        dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    }
    return dp[4];
};